package LeetCode.month01.day11;

import java.util.ArrayList;
import java.util.List;

public class No148 {

    public ListNode sortList2(ListNode head){
        if(head==null){
            return head;
        }
        int length = 0;
        ListNode curr = head;
        while(curr!=null){
            length++;
            curr = curr.next;
        }
        ListNode newhead = new ListNode(0,head);
        for (int sublength=1; sublength<=length; sublength<<=1) {
            curr = newhead.next;
            ListNode subhead = newhead;
            while(curr!=null){
                ListNode head1 = curr;
                for (int i = 1; i < sublength&&curr.next!=null; i++) {
                    curr = curr.next;
                }
                ListNode head2 =curr.next;
                curr.next = null;
                curr = head2;
                for (int i = 1; i < sublength&&curr!=null&&curr.next!=null; i++) {
                    curr = curr.next;
                }
                ListNode next = null;
                if(curr!=null) {
                    next = curr.next;
                    curr.next=null;
                }
                subhead.next = merge(head1,head2);
                while(subhead.next!=null){
                    subhead=subhead.next;
                }
                curr = next;
            }
        }
        return newhead.next;
    }

    public ListNode sortList1(ListNode head){
        if(head==null||head.next==null) return head;
        return sortList(head,null);
    }

    public ListNode sortList(ListNode head,ListNode tail){
        if(head==null) return head;
        if(head.next==tail){
            head.next =null;
            return head;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=tail){
            slow=slow.next;
            fast = fast.next;
            if(fast!=tail) fast = fast.next;;
        }
        ListNode mid = slow;
        ListNode l1 = sortList(head,mid);
        ListNode l2 = sortList(mid,tail);
        return merge(l1,l2);
    }
    public ListNode merge(ListNode l1,ListNode l2){
        ListNode newh = new ListNode(0);
        ListNode curr = newh;
        while(l1!=null&&l2!=null){
            if(l1.val<l2.val){
                curr.next = l1;
                l1 = l1.next;
                curr = curr.next;
            }else{
                curr.next = l2;
                l2 = l2.next;
                curr = curr.next;
            }
        }
        if(l1!=null){
            curr.next = l1;
        }
        if(l2!=null){
            curr.next = l2;
        }
        return newh.next;
    }

    public ListNode sortList(ListNode head) {
        if(head==null||head.next==null) return head;
        ArrayList<ListNode> list = new ArrayList<>();
        ListNode curr = head;
        while(curr!=null){
            list.add(curr);
            curr = curr.next;
        }
        ListNode[] arr =list.toArray(new ListNode[list.size()]);

        mergeSort(arr);
        head = arr[0];
        curr = head;
        for (int i = 1; i < arr.length; i++) {
            curr.next = arr[i];
            curr = curr.next;
        }
        curr.next = null;
        return head;


        //暴力超时
//        ListNode nhead = head;
//        while(nhead!=null){
//            ListNode curr = nhead.next;
//            while(curr!=null){
//                if(curr.val<nhead.val){
//                    int temp = curr.val;
//                    curr.val = nhead.val;
//                    nhead.val = temp;
//                }
//                curr = curr.next;
//            }
//            nhead = nhead.next;
//        }
//        return head;
    }


    //自写
    private void mergeSort(ListNode[] arr) {
        ListNode[] temp = new ListNode[arr.length];
        mergeSort(arr,0,arr.length-1,temp);
    }

    private void mergeSort(ListNode[] arr, int left, int right, ListNode[] temp) {
        if(left<right){
            int mid = left+(right-left)/2;
            mergeSort(arr,left,mid,temp);
            mergeSort(arr,mid+1,right,temp);
            merge(arr,left,mid,right,temp);
        }
    }

    private void merge(ListNode[] arr, int left, int mid, int right, ListNode[] temp) {
        int i = left;
        int j = mid+1;
        int k = 0;
        while(i<=mid&&j<=right){
            if(arr[i].val<arr[j].val) temp[k++] = arr[i++];
            else temp[k++] = arr[j++];
        }
        while(i<=mid){
            temp[k++] = arr[i++];
        }
        while(j<=right){
            temp[k++] = arr[j++];
        }
        System.arraycopy(temp,0,arr,left,k);
    }
}
